1. Field of the Invention
The present invention relates to a cryptographic checksum apparatus, and more particularly, to a cryptographic checksum circuit with conditional cross feedback of feedback shift registers (FSRs).
2. Description of the Prior Art
An article entitled A Fast Cryptographic Checksum Algorithm Based on Stream Ciphers, Proc. of the AUSCRYPT""92, December, 1992 by Xuejia Lai et al. discloses a simple and fast cryptographic checksum algorithm based on stream ciphers for the use of message authentication. The generated cryptographic checksum is used to detect active attacks on the communication channel to ensure data integrity. The Lai""s algorithm primarily applies conventional keyed-hash function to map variable-length input strings into fixed-length output strings, which are then used as the integrity authenticator.
For a known pair of message and checksum, an attacker can successfully find a valid pair of message and checksum with probability 1/2 by changing the last bit in the message and the last bit in the checksum. By inference, the attacker can also successfully find another valid pair of message and checksum with probability (1/2)t by changing the last t bits in the message and appropriate modification of the last t bits in the checksum. Accordingly, a postfixed format is generally required to prevent the possible forgery of obtaining valid pair of message and checksum. For practical applications, approximately 100 bits of postfixed format is required to achieve protection probability of 10xe2x88x9230. Unfortunately, such long length of the postfixed format will inevitably make the message receiving and transmission more complicated. For the foregoing reasons, there is a need for a cryptographic checksum apparatus with low forgery probability and short postfixed format, so that a shared common secret key can be used for a long period of time between a sender and a receiver for the purpose of authenticated communication.
In accordance with the present invention, a cryptographic checksum apparatus is provided to substantially reduce forgery probability.
Another object of the present invention is to provide a cryptographic circuit with short postfixed format and low forgery probability, so that a shared common secret key can be used for a long period of time between a sender and a receiver for the purpose of authenticated communication.
In one embodiment according to the present invention, the cryptographic checksum circuit includes a keystream generator configured to generate a secret keystream according to a common secret key, wherein the secret keystream includes a string of binary random numbers. The apparatus also includes a postfix circuit configured to augment postfix bits after an original message, thereby generating a postfixed message. Further, a demultiplexer having, for example, two output terminals is used to direct the postfixed message to one of the output terminals under the control of the secret keystream. A first mixer, such as a logic exclusive OR gate, is configured to receive the output of one output terminal of the demultiplexer, and a second mixer is configured to receive the output of the other output terminal of the demultiplexer. Moreover, a first compression circuit is used to receive an output of the first mixer, wherein the content of the first compression circuit is used as the first part of the checksum output. Similarly, a second compression circuit is used to receive an output of the second mixer, wherein the content of the second compression circuit is used as the second part of the checksum output. In the embodiment, the first compression circuit or the second compression circuit includes a shift register and a digital switch connected therebetween, wherein the output of the digital switch is fed to the corresponding compression circuit. Finally, a first transmission gate, such as a logic AND gate, is configured to receive an output bit of the second compression circuit, the output bit of the second compression circuit being then transferred to the first mixer through the first transmission gate under control of the postfixed message bit. A second transmission gate is configured to receive an output bit of the first compression circuit, the output bit of the first compression circuit being then transferred to the second mixer through said second transmission gate under control of the postfixed message bit.